【LeetCode 363】Max Sum of Rectangle No Larger Than K

发表于 | 分类于

[LeetCode 363] Max Sum of Rectangle No Larger Than K

Problem description:

Given a non-empty 2D matrix matrix and an integer k, find the max sum of a rectangle in the matrix such that its sum is no larger than k.

Note:
The input is an array of integers. Only the least significant 8 bits of each integer is used to store the data. This means each integer represents only 1 byte of data.

Example1:

1
2
3
4
5
Given matrix = [
  [1,  0, 1],
  [0, -2, 3]
]
k = 2

The answer is 2. Because the sum of rectangle [[0, 1], [-2, 3]] is 2 and 2 is the max number no larger than k (k = 2).

Note:

  1. The rectangle inside the matrix must have an area > 0.
  2. What if the number of rows is much larger than the number of columns?

问题描述:

给定一个非空的二位矩阵和一个整数K，找到矩阵中子矩阵和最大并且不超过k的最大值。

示例1:

1
2
3
4
5
给定矩阵 matrix = [
  [1,  0, 1],
  [0, -2, 3]
]
k = 2

答案是2，因为矩形[[0, 1], [-2, 3]]和是2并且2 是不超过k（k=2）的最大值 。

Solution1:

这道题用纯暴力只能过95%左右，后面几个用例都会超时，所以在暴力的基础上稍微改进一下即可通过。（但不是最优解，复杂度为O(N2M2)）

用一个新矩阵保存计算值，每个值表示从点（0,0）到（i,j）的和，则计算（x1,y1）到（x2,y2）的值有以下四种情况：

  • x1-1<0 && y1-1<0: 说明（x1,y1）即为（0,0）点，直接返回存储矩阵中s[x2][y2]的值

  • x1-1>=0 && y1-1<0: 说明y1=0， 

    1
    2
    3
    4
    5
    6
    1 2 3 4
    -------
    5 6 7 8
    0 1 2 9
    -------
    计算从（1,0）到（3，3）的值

    则返回s[x2][y2]-s[x1-1][y2]

  • x1-1<0 &&="" y1-1="">=0: 说明x1=0， 

    1
    2
    3
    4
    5
    1|2 3 4|
    5|6 7 8|
    0|1 2 9|

    计算从（0,1）到（3，3）的值

则返回s[x2][y2]-s[x2][y1-1]

  • x1-1>=0 && y1-1>=0:

    1
    2
    3
    4
    5
    1 2 3 4
     -------
    5|6 7 8|
    0|1 2 9|
     -------

则返回s[x2][y2]-(s[x1-1][y2]+s[x2][y1-1]-s[x1-1][y1-1])

遍历子矩阵用四层循环即可解决。

Code:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
class Solution {
    public int maxSumSubmatrix(int[][] matrix, int k) {


        int max=0;
        int row=matrix.length;
        int col=matrix[0].length;

        int [][]store=new int[row][col];
        for(int i=0;i<row;i++){
            for(int j=0;j<col;j++){
                store[i][j]=sum(matrix,0,0,i,j);
            }
        }


        boolean flag=true;
        for(int x=0;x<row;x++){
            for(int y=0;y<col;y++){
                for(int i=x;i<row;i++){
                    for(int j=y;j<col;j++){

                    int t=sSum(store,x,y,i,j);
                    if(t==k)
                        return t;
                    if(flag && t<k){
                        max=t;
                        flag=false;
                    }
                    if(t<k){
                    max=Math.max(t,max);

                    }
                }


            }

        }
    }
        return max;

    }

    public int sSum(int [][]s,int x1,int y1,int x2,int y2 ){
        if(x1-1<0 && y1-1<0)
            return s[x2][y2];
        if(x1-1>=0 && y1-1<0)
            return s[x2][y2]-s[x1-1][y2];
        if(x1-1<0 && y1-1>=0)
            return s[x2][y2]-s[x2][y1-1];
        else{
        return s[x2][y2]-(s[x1-1][y2]+s[x2][y1-1]-s[x1-1][y1-1]);
        }
    }
    public int sum(int [][]matrix,int x1,int y1,int x2,int y2){
        int res=0;
        for(int i=x1;i<=x2;i++){
            for(int j=y1;j<=y2;j++){  
                res+=matrix[i][j];
            }

        }
        return res;

    }
}

Solution2:动态递归解法（学习后补充）

首先使用动态规划解法，这道题目可以拆分成两道题。
第一点是求矩阵子矩阵最大和的动态规划思想，参考视频链接。

具体思想就是，按列扫描累加每一列然后求最大值，这样就转换为一维数组子数组求最大和的问题，这是一个简单的动态规划，dp[i]=max(dp[i-1],array[i]);

第二点就是一维数组子数组最大和有可能大于给定的k，所以问题转换为求一维数组子数组和不大于k的最大值：

通过累加和可以求得任意区间的和，例如，cum数组为累加和数组，cum[i]表示从cum[0]到cum[i]的和，则区间（i,j）的和可表示为cum[j]-cum[i-1];

这里还要借助TreeSet因为treeset中ceiling方法可以求出大于或等于给定的元素的最小元素，也就是说我们在累加过程中去比较max和set.ceiling(sum-k)的大小即可，由于treeset查询这一步时间复杂度是O(logn),所以总的时间复杂度是O(N2*M*log(M)),如果列数远远大于行数，可以按照行扫描。

Code:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
class Solution {
    public int maxSumSubmatrix(int[][] matrix, int k) {
        int rowSize=matrix.length;
        int colSize=matrix[0].length;
        int maxSum=Integer.MIN_VALUE;
        int currentSum=0;
        
       // int maxLeft=0;
       // int maxRight=0;
       //  int maxUp=0;
       //  int maxDown=0;
        
        int []rowArray=new int[rowSize];
        for(int left=0;left<colSize;left++){
            for(int right=left;right<colSize;right++){
                for(int i=0;i<rowSize;i++){
                    rowArray[i]+=matrix[i][right];
                }
                
                
                currentSum=maxSubArray(rowArray,k);
                
                if(currentSum==k)
                    return k;
                
                if(currentSum<k)
                    maxSum=Math.max(currentSum,maxSum);
            }
            for(int i=0;i<rowSize;i++){
                    rowArray[i]=0;
                }
        }
        return maxSum;
    }
    public int maxSubArray(int []a,int k){
       TreeSet<Integer> set=new TreeSet<Integer>();
        int sum=0;
        int max=Integer.MIN_VALUE;
        set.add(0);
       for(int i=0;i<a.length;i++){
           sum+=a[i];
           Integer v=set.ceiling(sum-k);//返回大于或等于给定的元素的最小元素，或null
           if(v!=null){
               max=Math.max(sum-v,max);
           }
           set.add(sum);
           
       } 
        return max;
        
    }
    
}
Thanks!